The present invention relates generally to halftoning of input image data and is particularly directed to generating a stochastic dither array of the type which generates clusters of dots. The invention is specifically disclosed as a method for generating clustered dots using an xe2x80x9coverallxe2x80x9d weighting function derived from two functions of two different extents which are subtracted from one another, so that small clusters of dots are formed at locations near a center of the overall weighting function, but at a predetermined radius from this center the overall weighting function limits the chance of such locations from being selected.
Halftoning describes the algorithmic process of displaying an image on a device that is capable of representing only a finite, discrete number of tone levels. The position and arrangement of the discrete picture elements should create the illusion of a continuous-tone image (see, Ulichney, xe2x80x9cDigital Halftoning,xe2x80x9d MIT Press (1987)). Traditional halftoning techniques include clustered-dot ordered dithering, dispersed-dot ordered dithering, and error diffusion.
More recent halftoning techniques include a method using dispersed-dot unordered dithering, which is also known as stochastic dithering, which combines the speed of a dither array with a quality approaching that of error diffusion. Examples of stochastic dithering include: Sullivan and Ray""s Correlated Minimum Visual Modulation Patterns (see U.S. Pat. No. 5,214,517), and Sullivan, Ray, and Miller""s, xe2x80x9cDesign of Minimum Visual Modulation Halftone Patterns,xe2x80x9d published by IEEE Transactions on Systems, Man and Cybernetics, Volume 21, No. 1, pages 33-38 (January/February 1991)); Parker and Mitsa""s Blue Noise Mask (see U.S. Pat. No. 5,111,310); Mitsa and Parker, xe2x80x9cDigital Halftoning Technique Using a Blue-Noise Mask,xe2x80x9d published in J. Opt. Soc. Am., Volume 9, No. 11, pages 1920-1929 (November 1992)); Ulichney""s Void and Cluster Algorithm (see U.S. Pat. No. 5,535,020); Ulichney, xe2x80x9cThe Void-and-Cluster Method for Dither Array Generation,xe2x80x9d Proceedings of the SPIE, Volume 1913, pages 332-343 (September 1993)); and Cooper, Knight, and Love""s Minimum Density Variance Method (see U.S. Pat. No. 5,696,606).
Although stochastic dithering performs well in many circumstances, it has certain limitations related to the physical printing process. Similar to conventional error diffusion, stochastic dithering requires reliable reproduction of dispersed dots. However, printers often have difficulty rendering individual, dispersed dots consistently (especially laser or other electrophotographic printers). This causes variation in uniformity and tone. On the other hand, clustered dots, as opposed to dispersed dots, may be rendered with much greater consistency. It could be a significant advantage for certain physical printers to use a hybrid version of halftoning that uses clustered-dot, unordered dithering.
Some clustered-dot unordered (stochastic) dithering methods are beginning to appear. Ostromoukhov may have the earliest such approach, based upon Voronoi polygons. See Ostromoukhov, xe2x80x9cPseudo-Random Halftone Screening for Color and Black and White Printing,xe2x80x9d published in Recent Progress in Digital Halftoning, edited by Eschbach, pages 130-134 (1994)xe2x80x94originally in Proceedings of ISandT""s 9th Non-Impact Printing Conference held on Oct. 4-8, 1993.
More recently, Lau has extended the green noise halftoning approach to generate dither arrays (see Lau, Arce, and Gallagher, xe2x80x9cDigital Halftoning Via Green Noise Masks,xe2x80x9d to appear in J. Opt. Soc. Am. A, 1999). Lau et al. have filed corresponding patent applications in the United States, see application Ser. Nos. 60/071,649 (filed Jan. 16, 1998) and 09/228,573 (filed Jan. 11, 1999).
Two other documents of interest regarding blue noise dither matrices are, xe2x80x9cMethods for Generating Blue-Noise Dither Matrices for Digital Halftoning,xe2x80x9d by Spaulding, Miller, and Schildkraut, J. of Electronic Imaging, Volume 6, No. 2, pages 208-230 (April 1997); and Wang and Parker, xe2x80x9cProperties of Jointly-Blue Noise Masks and Application on Color Halftoning,xe2x80x9d Proceedings of ISandT/SID Seventh Color Imaging Conference, pages 188-193 (November 1999).
Another interesting patent application is WO 99/45697 (by Nilsson), which discloses the use of a band-pass filter to modify the mid-tones of the gray levels used in halftoning an image. FIGS. 5 and 7 disclose some interesting maps used for halftoning.
A conventional void and cluster algorithm begins with an arbitrary dot pattern, typically consisting of a random arrangement of dots. These dots are then repositioned iteratively until the dots are properly dispersed. This becomes the initial dot pattern. A dither array is now constructed, and dots are removed sequentially from the dot pattern. Each time a dot is removed, its location is marked in the dither array with the appropriate threshold level. Once all dots have been removed, the initial dot pattern is restored. Dots are now added sequentially, while marking the corresponding location in the dither array with the appropriate threshold level.
To disperse the original dot pattern, the largest void (i.e., concentration of non-dots, or xe2x80x9cholesxe2x80x9d) and the largest cluster (i.e., concentration of dots) are identified. (It should be noted that, in the context of a void and cluster algorithm, a xe2x80x9cclusterxe2x80x9d is a concentration of dotsxe2x80x94the dots need not be physically adjacent.) The pixels at these two locations are swapped, in which the dot located at the largest cluster is moved to the location of the largest void. This process continues iteratively until the swap will turn the largest void into the largest cluster, and vice versa. The result is a dot pattern with the same number of dots as the initial pattern, but with the dots spread out from one another (i.e., dispersed) in a visually pleasing manner.
The process of constructing a threshold array from the initial dot pattern is similar. Dots are removed from the locations forming the largest clusters, and dots are added to the locations forming the largest voids. To locate the largest void and the largest cluster, a simple two-dimensional Gaussian weighting function is used. This weighting function is shifted so that its peak is centered at the location of a dot. (It should be noted that the weighting function, like the threshold array, must be periodic.) For each dot in the image, a shifted weighting function will be accumulated. The smallest and largest values, respectively, determine the void and cluster of the given dot pattern.
The largest void may not necessarily be located at a hole, nor must the largest cluster be located at a dot. For example, suppose that the binary image consists of only four (4) dots, arranged in a cross with a hole in the center. The largest cluster would be located at the center of the cross, which of course means that the cluster is not located at a dot. Obviously, a dot cannot be added to a location which already contains a dot, nor may a dot be removed from a location that is already empty.
As described above, the void and cluster algorithm uses a Gaussian weighting function to determine the location at which each dot should be added or removed. This will yield a dither arrayxe2x80x94potentially a stochastic dither arrayxe2x80x94consisting of dispersed dots. However, it is possible to modify the weighting function so that a stochastic dither array of clustered dots is instead formed.
It would be an advantage to provide a new method for generating a clustered-dot, stochastic dither array, in the context of a void and cluster algorithm, understanding that this concept can be applied equally well to other existing stochastic dither array algorithms, such as the minimum density variance method.
Accordingly, it is an advantage of the present invention to provide a void and cluster-type algorithm that uses a novel weighting function that yields a dither array of clustered dots.
It is another advantage of the present invention to provide a weighting function that will create a stochastic dither array of clustered dots, rather than creating dispersed dots.
It is another advantage of the present invention to provide a methodology by which a pair of functions, in which the extent of one function is larger than the other, is used to generate a weighting function used for halftoning.
It is yet another advantage of the present invention to provide a weighting function that creates clusters of dots in which the weighting function reaches a minima at a center, then, as the distance from the center increases, the function increases and reaches a maximum or maxima, and thereafter the function decreases as the distance from the center further increases.
It is a further advantage of the present invention to provide a weighting function that uses two Gaussian functions, or two hyperbolic tangent functions, or a mixture of these functions, or two other types of functions that exhibit a maximizing and a minimizing effect when one such function is subtracted from the other.
It is yet a further advantage of the present invention to provide a weighting function that creates clusters when used with a minimum density variance methodology of creating a dither array, in which the cost function is the difference between two density sum arrays, or the difference between two delta density sum arrays.
It is still a further advantage of the present invention to provide a method for creating a clustered-dot dither array which rotates the clusters by an angle to either produce a special effect, or to be more readily discernible by the human visual system.
It is still another advantage of the present invention to create a clustered-dot dither array that creates a non-circular profile, such as an ellipse.
It is yet another advantage of the present invention to filter everything but shapes that are not orthogonal, which would eliminate a step of rotating the cluster in some circumstances.
Additional advantages and other novel features of the invention will be set forth in part in the description that follows and in part will become apparent to those skilled in the art upon examination of the following or may be learned with the practice of the invention.
To achieve the foregoing and other advantages, and in accordance with one aspect of the present invention, a method for halftoning is provided for use with a computer system, in which the method comprises: (a) providing a first function of a first extent and a second function of a second extent, wherein the first extent is not equal to the second extent, and subtracting the second function from the first function to thereby derive a weighting function; and (b) halftoning input data using the weighting function to create at least one dot cluster, wherein, at each dot cluster, the weighting function reaches at least one first minima at substantially a center position, then increases to at least one maximum along a path directed away from the center position, and finally decreases toward at least one second minima further along the path.
In accordance with another aspect of the present invention, a method for halftoning is provided for use with a computer system, in which the method comprises: (a) providing a first minimization function and a second maximization function, wherein the first and second functions are not equal to one another, and subtracting the second function from the first function to thereby derive a weighting function; and (b) halftoning input data using the weighting function to create at least one dot cluster, wherein, at each dot cluster, the weighting function reaches at least one first minima at substantially a center position, then increases to at least one maximum along a path directed away from the center position, and finally decreases toward at least one second minima further along the path.
Still other advantages of the present invention will become apparent to those skilled in this art from the following description and drawings wherein there is described and shown a preferred embodiment of this invention in one of the best modes contemplated for carrying out the invention. As will be realized, the invention is capable of other different embodiments, and its several details are capable of modification in various, obvious aspects all without departing from the invention. Accordingly, the drawings and descriptions will be regarded as illustrative in nature and not as restrictive.